#
# 递归解法：
# 这种思路比较容易
# 就是写一个函数按中序遍历的方法去递归调用就好
#
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ret = []
        def traversal(node, ret):
            if not node:
                return
            traversal(node.left, ret)
            ret.append(node.val)
            traversal(node.right, ret)
        traversal(root, ret)
        return ret


#
# 迭代解法：
# 这种思路老实说不好想
# 我是没想出来，看了题解还有点晕
# 先把解法放出来
#
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack, ret = [], []
        cur = root
        while stack or cur: #[]居然是False
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                ret.append(cur.val)
                cur = cur.right
        return ret
